package data_structure.leetcode;

import java.util.Random;

public class Solution215 {

    Random random = new Random();

    public int findKthLargest(int[] nums, int k){
        return findKthLargest (nums,k,0,nums.length-1);
    }

    public int findKthLargest(int[] nums, int k,int left,int right) {
        int partition=partition (nums,left,right);
        if(partition+1==k){
            return nums[partition];
        }else if(partition+1<k){
            return findKthLargest (nums,k,partition+1,right);
        }else{
            return findKthLargest (nums,k,left,partition-1);
        }
    }

    private int partition(int []arr,int left,int right){
        int partition=left+random.nextInt (right-left+1);
        swap (arr,left,partition);
        int i=left+1;
        int j=right;
        //大到小
        while(true){
            while(i<=j&&arr[i]>arr[left]){
                i++;
            }
            while (j>=i&&arr[j]<arr[left]){
                j--;
            }

            if(i>=j){
                break;

            }
            swap (arr,i,j);
            i++;
            j--;
        }
        swap (arr,left,j);
        return j;
    }

    private void swap(int []arr,int left,int right){
        int temp=arr[left];
        arr[left] = arr[right];
        arr[right] = temp;
    }
}
